Statement#

Suppose there is a game where a player can score either 11, 22, or 44 points in each turn. Given a total score, nn, find all the possible ways in which you can score these nn points.

Note: You may assume that you can use a specific score as many times as you want. Additionally, the order in which we select scores from the list is significant.

Let's say the total points to be earned are 33. A player can score this total in the following three ways:

  • 1,11, 1and 11, in three turns: 1+1+1=31+1+1 = 3.

  • 11 and then a 22, in two turns: 1+2=31 + 2 = 3.

  • 22 and then a 11, in two turns: 2+1=32 + 1 = 3.

Constraints:

  • 00 <= nn <= 900900

Examples#

No.

Points

Total Points

Number of Ways

1

[1, 2, 4]

5

10

2

[1, 2, 4]

7

31

3

[1, 2, 4]

0

1

Try it yourself#

Implement your solution in the following playground.

Python
usercode > main.py
Input #1
Count Ways to Score in a Game

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Recursive Numbers dynamic programming pattern.

Naive approach#

A naive approach to solving this problem would be to make all the possible permutations of available points to reach the target score, so let's first figure out the recurrence relation for this problem.

As we can only score 11, 22, or 44 in each turn, to reach a score of nn, we can only use increments of 11, 22, or 44 in each turn. To reach a total score of nn, we have the following three possibilities:

  • Number of ways to reach n1n - 1, as we can then add 11 to reach nn

  • Number of ways to reach n2n-2, as we can then add 22 to reach nn

  • Number of ways to reach n4n-4, as we can then add 44 to reach nn

These all are valid ways to reach a score of nn. We can now sum them up to get all the possible ways to reach a total score of nn.

As per the above points, we can derive the following recurrence relation for this problem:

           S(n)=S(n1)+S(n2)+S(n4)S(n)=S(n-1)+S(n-2)+S(n-4)

Here, S(n)S(n) is the number of ways of reaching a total score of nn.

Now, let's look at the code in the code widget below for the solution we just discussed.

Count Ways to Score in a Game using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of this solution is O(2n)O(2^n).

Space complexity#

The space complexity of this solution is O(n)O(n) because each recursive call consumes memory on the stack, and the longest call stack corresponds to the calls starting from nn, through n1n-1, n2n-2, down to 33, 22 and 11.

Optimized solution using dynamic programming#

As the recursive solution to this problem is very costly, let's see if we can reduce this cost in any way. Dynamic programming helps us to avoid recomputing the same subproblems. Let's analyze our recursive solution to see if it has the properties needed for conversion to dynamic programming.

  • Optimal substructure: If we wanted to find the solution to the problem of counting a total score, nn, given pp different points, and we knew the answer to the pp subproblems formed by subtracting each of the pp points from the total score S, we could simply sum up the answer to these subproblems, and that would give us the answer to our original problem. Therefore, this problem obeys the optimal substructure property.

  • Overlapping subproblems: The algorithm solves the same subproblems again and again, so it does have the second property of dynamic programming as well.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating solutions to subproblems over and over again by storing the subproblem solutions, and reusing the stored solutions when the same subproblem is encountered again. Therefore, the only addition to this algorithm compared to the simple recursive one is the addition of memoization. Specifically, we build the solution top-down and store the found results in a memo array.

The slides below are to help you visualize the process. Here, the green nodes represent recursive calls where stored results are fetched from the memo array:

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo -1 -1 -1 -1 -1 -1 S(5)

1 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo -1 -1 -1 -1 -1 -1 S(5) S(4)

2 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo -1 -1 -1 -1 -1 -1 S(5) S(4) S(3)

3 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo -1 -1 -1 -1 -1 -1 S(5) S(4) S(3) S(2)

4 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo -1 -1 -1 -1 -1 -1 S(5) S(4) S(3) S(2) S(1)

5 of 16

Created with Fabric.js 3.6.6 S(5) S(4) S(3) S(2) S(1) S(0) = 1 index 0 1 2 3 4 5 memo 1 -1 -1 -1 -1 -1 Please note that as per our first base case, we add 1 for the score 0. This is because there is only one way to score 0, that is, by not playing any move or not scoring any of the available scores.

6 of 16

Created with Fabric.js 3.6.6 S(5) S(4) S(3) S(2) S(1) S(0) = 1 S(-1) = 0 index 0 1 2 3 4 5 memo 1 -1 -1 -1 -1 -1 As per our second base case, we return 0 for thenegative scores.

7 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo 1 1 -1 -1 -1 -1 S(5) S(4) S(3) S(2) S(1) S(0) = 1 S(-1) = 0 S(-3) = 0

8 of 16

Created with Fabric.js 3.6.6 S(5) S(4) S(3) S(2) S(1) S(0) = 1 S(0) = 1 S(-1) = 0 S(-3) = 0 index 0 1 2 3 4 5 memo 1 1 -1 -1 -1 -1 We had stored the result of S(0) in memo, so we reuse that result.

9 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo 1 1 2 -1 -1 -1 S(5) S(4) S(3) S(2) S(1) S(0) = 1 S(-2) = 0 S(0) = 1 S(-1) = 0 S(-3) = 0

10 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo 1 1 2 -1 -1 -1 S(5) S(4) S(3) S(2) S(1) = 1 S(1) S(0) = 1 S(-2) = 0 S(0) = 1 S(-1) = 0 S(-3) = 0

11 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo 1 1 2 3 -1 -1 S(5) S(4) S(3) S(2) S(1) = 1 S(-1) = 0 S(1) S(0) = 1 S(-2) = 0 S(0) = 1 S(-1) = 0 S(-3) = 0

12 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo 1 1 2 3 -1 -1 S(5) S(4) S(3) S(2) = 2 S(2) S(1) = 1 S(-1) = 0 S(1) S(0) = 1 S(-2) = 0 S(0) = 1 S(-1) = 0 S(-3) = 0

13 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo 1 1 2 3 6 -1 S(5) S(4) S(3) S(2) = 2 S(0) = 1 S(2) S(1) = 1 S(-1) = 0 S(1) S(0) = 1 S(-2) = 0 S(0) = 1 S(-1) = 0 S(-3) = 0

14 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo 1 1 2 3 6 -1 S(5) S(4) S(3) = 3 S(3) S(2) = 2 S(0) = 1 S(2) S(1) = 1 S(-1) = 0 S(1) S(0) = 1 S(-2) = 0 S(0) = 1 S(-1) = 0 S(-3) = 0

15 of 16

Created with Fabric.js 3.6.6 index 0 1 2 3 4 5 memo 1 1 2 3 6 10 S(5) S(4) S(3) = 3 S(1) = 1 S(3) S(2) = 2 S(0) = 1 S(2) S(1) = 1 S(-1) = 0 S(1) S(0) = 1 S(-2) = 0 S(0) = 1 S(-1) = 0 S(-3) = 0

16 of 16

Now, let's look at the code in the code widget below for the solution we just discussed.

Count Ways to Score in a Game using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of this solution is O(n)O(n).

Space complexity#

The space complexity of this solution is O(n)O(n).

Bottom-up solution#

Let’s look at the bottom-up dynamic programming approach to solving this problem. The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. Here, we iteratively build the solution in a bottom-up direction by storing the results in a fixed-size array.

We first create and initialize the fixed array, dp, that will store our results. Then, we set dp[0] to 1, which is our base case, that is, there is only one way to reach a score of 00 by not playing any moves.

To calculate the result for any turn, we sum up the number of ways to get a score of n1n-1, n2n−2, and n4n-4. This is similar to our recurrence relation. For example, to find the number of ways to score 55, we add up dp[5-1], dp[5-2] and dp[5-4]. During the calculations, if at any point, the remaining value needed to reach nn becomes negative, we will simply return 00, as there is no way to reach a negative score.

Let's look at how this technique works for a total score of 55:

Created with Fabric.js 3.6.6 Let's try to calculate the number of ways to reach a score of 5. 0 1 2 3 4 5 0 0 0 0 0 0

1 of 10

Created with Fabric.js 3.6.6 0 1 2 3 4 5 1 0 0 0 0 0 We have set up our array with the basecase. There is only one way to reach a score of 0.

2 of 10

Created with Fabric.js 3.6.6 Let's look at the process for getting the value for n = 1. We will use the following:array[n] = array[n-1] + array[n-2] + array[n-4] 0 1 2 3 4 5 1 0 0 0 0 0

3 of 10

Created with Fabric.js 3.6.6 We will use 0 for negative index values.array[1] = array[1-1] + array[1-2] + array[1-4]array[1] = array[0] + array[-1] + array[-3]array[1] = 1 + 0 + 0 0 1 2 3 4 5 1 0 0 0 0 0

4 of 10

Created with Fabric.js 3.6.6 array[1] = 1We can calculate the rest of the values ofthe array similarly. 0 1 2 3 4 5 1 1 0 0 0 0

5 of 10

Created with Fabric.js 3.6.6 array[2] = array[2-1] + array[2-2] + array[2-4]array[2] = array[1] + array[0] + array[-2]array[2] = 1 + 1 + 0array[2] = 2 0 1 2 3 4 5 1 1 2 0 0 0

6 of 10

Created with Fabric.js 3.6.6 array[3] = array[3-1] + array[3-2] + array[3-4]array[3] = array[2] + array[1] + array[-1]array[3] = 2 + 1 + 0array[3] = 3 0 1 2 3 4 5 1 1 2 3 0 0

7 of 10

Created with Fabric.js 3.6.6 array[4] = array[4-1] + array[4-2] + array[4-4]array[4] = array[3] + array[2] + array[0]array[4] = 3 + 2 + 1array[4] = 6 0 1 2 3 4 5 1 1 2 3 6 0

8 of 10

Created with Fabric.js 3.6.6 array[5] = array[5-1] + array[5-2] + array[5-4]array[5] = array[4] + array[3] + array[1]array[5] = 6 + 3 + 1array[5] = 10 0 1 2 3 4 5 1 1 2 3 6 10

9 of 10

Created with Fabric.js 3.6.6 0 1 2 3 4 5 1 1 2 3 6 10 We now have the total number of ways, 10, ofreaching a score of 5.

10 of 10

Let's have a look at the code for the bottom-up approach as well.

Count Ways to Score in a Game using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of this solution is O(n)O(n).

Space complexity#

The space complexity of this solution is O(n)O(n).

Number Factors

Unique Paths to Goal